let arr = [4,3,2,1]
let arrr = mergeSort(arr)
console.log(arrr)

function mergeSort(arr){
    var len = arr.length
    if(len < 2){
        return arr
    }
    var middle = Math.floor(len/2)
    var left = arr.slice(0,middle)
    var right = arr.slice(middle)
    return merge(mergeSort(left),mergeSort(right))
}

function merge(left,right){
    var result = []
    while(left.length>0 && right.length>0){
        if(left[0] <= right[0]){
            result.push(left.shift())
        }else{
            result.push(right.shift())
        }
    }
    while(left.length){
        result.push(left.shift())
    }
    while(right.length){
        result.push(right.shift())
    }
    return result
}

/*
时间复杂度   O(nlogn)
最大        O(nlogn)
最小        O(nlogn)
稳定
空间复杂度   O(n)
*/